import math;
import copy;
import configuration;

#turning 180 not allowed, non-cardinal (nsew) directions not allowed
#any mismatches will return an error
def calc_turn(firstDirection, secondDirection):
    if(firstDirection == secondDirection):
        return 'None'
    if(firstDirection == 'north'):
        if(secondDirection == 'east'):
            return 'turn right '
        elif(secondDirection == 'west'):
            return 'turn left '
    if(firstDirection == 'south'):
        if(secondDirection == 'east'):
            return 'turn left '
        elif(secondDirection == 'west'):
            return 'turn right '
    if(firstDirection == 'east'):
        if(secondDirection == 'north'):
            return 'turn left '
        elif(secondDirection == 'south'):
            return 'turn right '
    if(firstDirection == 'west'):
        if(secondDirection == 'north'):
            return 'turn right '
        elif(secondDirection == 'south'):
            return 'turn left '
    return 'Error'

class NavNode:
    def __init__ (self, x, y, inNeighbors, name, type):
        self._xCoord = x
        self._yCoord = y
        self._neighbors = inNeighbors
        self._name = name
        self._type = type

    def calc_distance(self, node):
        x = node.get_x()
        y = node.get_y()
        return math.sqrt(math.pow((self._xCoord - x),2) + math.pow((self._yCoord - y), 2))

    def calc_direction(self, node):
        x = node.get_x()
        y = node.get_y()
        deltaX = (self._xCoord - x)
        deltaY = (self._yCoord - y)
        direction = ""
        if(deltaY > 0): #south
            direction = direction + "south"
        elif(deltaY < 0):#north
            direction = direction + "north"
        if(deltaX > 0): # west
            direction = direction + "west"
        elif(deltaX < 0): #east
            direction = direction + "east"
        return direction

    def get_x(self):
        return self._xCoord

    def get_y(self):
        return self._yCoord

    def get_neighbors(self):
        return self._neighbors

    def get_name(self):
        return self._name

    def get_type(self):
        return self._type


class Graph:
    _nodes = {}
    def __init__(self):
        configFile = configuration.yaml_configuration('navyaml.yaml') #TODO update this to a url?
        config = configFile.getConfiguration()
        nodeList = []
        for data in config:
            n = NavNode(data['x'], data['y'], data['neighbors'], data['name'], data['type'])
            nodeList.append(n)
        for n in nodeList:
            self._nodes[n.get_name()] = n
#               self._nodes = nodes

    def add(self, node):
        self._nodes[node.get_name()] = node

    def navigate(self, src, dest):
#src and dest are strings that correspond to the name of the node we will be navigating
#               to and from
        dist = {}
        previous = {}
        remainingDist = {}
        for node in self._nodes:
            #initialize the distance and previous lists
            dist[node] = 999999
            remainingDist[node] = 999999
            previous[node] = 999999
        dist[src] = 0
        remainingDist[src] = 0
        #loop while we still have nodes left in the set to process
        while remainingDist.keys() != []:
            #This node is the node with the smallest distance value that we haven't processed yet
            minDistNode = min(remainingDist,key = lambda a: remainingDist.get(a))

            if (dist[minDistNode] == 999999):
                break;#no more nodes are accessible from src
            for n in self._nodes[minDistNode].get_neighbors():
                #process all of the neighbors of this node
                #print minDistNode
                #print self._nodes[n]
                alt = dist[minDistNode] + self._nodes[minDistNode].calc_distance(self._nodes[n])
                if alt < dist[n]:
                    #if the new distance is shorter, update the distance and previous values
                    dist[n] = alt
                    remainingDist[n] = alt
                    previous[n] = minDistNode
            #remove the processed node from the distance list
            del remainingDist[minDistNode]

        temp = previous[dest]
        arr1 = [dest]
        arr2 = []
        #get the list of the path to the destination, backwards
        while(temp != src):
            arr1.append(temp)
            temp = previous[temp]
        if(temp == src):
            arr1.append(temp)

        #reverse the list
        while len(arr1) != 0:
            arr2.append(arr1.pop())
        return arr2

    def get_text_path(self, path):

        length = len(path)
        if length < 2:
            return "Bad path"
        dest = path[len(path)-1]
        workingPath = copy.deepcopy(path)
        direction = ""
        textPath = []
        firstNode = self._nodes[path[0]]
        if(firstNode.get_type() == 'office'):
            textPath.append('Leave the office and ')
        elif(firstNode.get_type() == 'cluster'):
            textPath.append('Leave the cluster and ')
        print self._nodes[path[0]].get_type()
        first = 0
        for n in workingPath:
            if(first == 0):
                first = 1
                continue
            if(first == 1):
                nextNode = self._nodes[n]
                firstDir = firstNode.calc_direction(nextNode)
                firstNode = nextNode
                first = 2
                continue

            nextNode = self._nodes[n]

            secondDir = firstNode.calc_direction(nextNode)
            #print secondDir + ' is the direction from ' + firstNode.get_name() + ' to ' + nextNode.get_name()
            turn = calc_turn(firstDir, secondDir)
            if(n == dest):
                if(turn == 'None'):
                    textPath.append('Arrive at your destination ahead')
                else:
                    textPath.append('Arrive at your destination on the ')
                    if(turn == 'turn right '):
                        textPath.append('right\n');
                    if(turn == 'turn left '):
                        textPath.append('left\n');
            elif(turn != 'None'):

                textPath.append(turn)
                name = firstNode.get_name()
                if(name == 'ae1' or name == 'ec1' or name == 'cd1' or name == 'ad1'):
                    textPath.append('at the end of the hall')
                else:
                    if(name == 'eb1' or name == 'bd1'):
                        if(nextNode.get_name() == 'b8' and name == 'bd1'):
                            textPath.append('at the next hall')
                        elif(nextNode.get_name() == 'b1' and name == 'eb1'):
                            textPath.append('at the next hall')
                        else:
                            textPath.append('at the end of the hall')
                textPath.append('\n')
            firstDir = secondDir
            firstNode = nextNode
            #print turn

            #print n
        #if(turn == 'None'):
        #       textPath.append('arrive ')
        #textPath.append('at your destination\n')
        return textPath

    def get_distance(self, path):
        first = 0
        node1 = path[0] # initialization
        node2 = path[0] # initialization
        dist = 0
        for n in path:
            if first == 0:
                first = 1
                node1 = n
                continue
            if first == 1:
                first = 2
                node2 = n
                continue
            dist = dist + self._nodes[node1].calc_distance(self._nodes[node2])
            node1 = node2
            node2 = n
        dist = dist + self._nodes[node1].calc_distance(self._nodes[node2])
        return dist

    def nearest_restroom(self, node):
        shortest = 0
        retpath = []
        for n in self._nodes:
            if self._nodes[n].get_type() == 'restroom':
                path = self.navigate(node, n)
                distance = self.get_distance(path)
                if(distance < shortest or shortest == 0):
                    shortest = distance
                    retpath = path
                print self.get_distance(path)
        return retpath

    def nearest_printer(self, node):
        shortest = 0
        retpath = []
        for n in self._nodes:
            if self._nodes[n].get_type() == 'printer':
                path = self.navigate(node, n)
                distance = self.get_distance(path)
                if(distance < shortest or shortest == 0):
                    shortest = distance
                    retpath = path
                print self.get_distance(path)
        return retpath

    def nav_str(self, src, dst):
        if(dst == 'printer'):
            path = self.nearest_printer(src)
        elif(dst == 'restroom'):
            path = self.nearest_restroom(src)
        else:
            path = self.navigate(src, dst)
        text = self.get_text_path(path)
        retStr = ''
        for s in text:
            retStr = retStr + s
        print retStr
        return retStr

#begin debug code
'''
g = Graph()
print g.navigate('office108', 'office128')
g.get_text_path( g.navigate('office108', 'office128') )
print g.nearest_printer('office108')
g.get_text_path(g.nearest_printer('office108'))
print g.nav_str('office108', 'printer')
print g.nav_str('office108', 'office128')
'''
#end debug code
